from numpy import *

class NumpySet(object):
    def __init__(self, size, state='full'):
        self.size = size
        self.buffer = arange(0, size, dtype=int)
        self.indexof = arange(0, size, dtype=int)
        if state == 'full':
            self.count = size
        else:
            self.count = 0

    def __len__(self): return self.count

    def add(self, id):
        assert self.count < self.size
        self.indexof[id] = self.count
        self.buffer[self.count] = id
        self.count += 1

    def remove(self, id):
        pos = self.indexof[id]
        assert pos < self.count
        self.count -= 1
        movedid = self.buffer[pos] = self.buffer[self.count]
        if movedid != id:
            self.indexof[ movedid ] = pos

    def pick(self):
        assert self.count
        self.count -= 1
        return self.buffer[self.count]

    def getNextToPick( self ): return self.buffer[self.count-1]

    def getAsMask(self): return self.buffer[:self.count]

NEXT = 1
PREV = 0
FIRST = (-2, NEXT)
LAST = (-1, PREV)

class FadeBuffer(object):
    def __init__(self, size): #, buffers=[]): # buffers = [ (3, float32), (2, 2, int) ]
        self.alpha = zeros( (size,), float32)
        #self.buffers = [ zeros( (size,) + b[:-1], b[-1] ) for b in buffers ]
        self.used = NumpySet(size, state='empty')
        self.available = NumpySet(size, state='full')
        self.order = zeros( (size + 2, 2), int )
        self.order[-2] = (0,-1)
        self.order[-1] = (-2,0)
        #self.first = self.last = None

    def full(self): return len(self.available) == 0

    def free(self, id):
        self.used.remove( id )
        self.available.add( id )
        p, n = self.order[id,PREV], self.order[id,NEXT]
        self.order[p,NEXT] = self.order[id,NEXT]
        self.order[n,PREV] = self.order[id,PREV]

    def alloc(self):
        assert not self.full()
        id = self.available.pick()
        self.order[id,NEXT] = -1
        self.order[id,PREV] = self.order[-1,PREV]
        self.order[ self.order[-1,PREV] ,NEXT] = id
        self.order[-1,PREV] = id
        self.used.add(id)
        return id

    def moveToFront(self, id):
        p, n = self.order[id,PREV], self.order[id,NEXT]
        self.order[p,NEXT] = self.order[id,NEXT]
        self.order[n,PREV] = self.order[id,PREV]
        self.order[id,NEXT] = -1
        self.order[id,PREV] = self.order[-1,PREV]
        self.order[ self.order[-1,PREV] ,NEXT] = id
        self.order[-1,PREV] = id
        self.alpha[id] = 1.0

    def forceOneOut(self):
        assert self.order[FIRST] >= 0
        pos = self.order[FIRST]
        self.free( pos )
        return pos

    def append(self): #, values = []):
        pos = self.alloc()
        self.alpha[pos] = 1.0
        #for i, val in enumerate(values):
        #    self.buffers[i][pos] = val
        return pos

    def nextPosition(self): return self.available.getNextToPick()
    def getMask(self): return self.used.getAsMask()

    def fadeOff(self, fade):
        mask = self.getMask()
        activealphas = self.alpha[mask]
        activealphas -= fade
        activealphas.clip(0, 1, out=activealphas)
        self.alpha[mask] = activealphas

    def removeDead(self):
        removed = []
        current = self.order[FIRST]
        while current >= 0 and self.alpha[current] <= 0.0:
            removed.append( current )
            self.free( current )
            current = self.order[current,NEXT]
        return removed

    def plot(self):
        print self.alpha[self.used.getAsMask()]


#buf = FadeBuffer(11, [(3, float32)])
#for i in xrange(300):
#    buf.update(0.05)
#    buf.plot()
#    er = buf.removeDead()
#    if er: 
#        print 'erase', er
#        buf.plot()
#    if (i% 4) == 0: 
#        if buf.full(): buf.forceOneOut()
#        buf.append( [(0,1,0)] )
#    if i == 100: buf.alpha[:] = 0.0

